package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1178 {
    public long startExecuteTime = System.currentTimeMillis();

// 单词 word 中包含谜面 puzzle 的第一个字母。
// 单词 word 中的每一个字母都可以在谜面 puzzle 中找到。

    //输入：
//words = ["aaaa","asas","able","ability","actt","actor","access"],
//puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
//输出：[1,1,3,2,4,0]
//解释：
//1 个单词可以作为 "aboveyz" 的谜底 : "aaaa"
//1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"

//3 个单词可以作为 "abslute" 的谜底 : "a", "as", "abel"      abelstu
//2 个单词可以作为 "absoryz" 的谜底 : "a", "as"
//4 个单词可以作为 "actresz" 的谜底 : "a", "as", "act", "aces"
//没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 而自己的代码又超时，不具备先进性
     * @return:
     */
    class Solution {
        public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
            Map<Integer, Integer> frequency = new HashMap<Integer, Integer>();

            for (String word : words) {
                int mask = 0;
                for (int i = 0; i < word.length(); ++i) {
                    char ch = word.charAt(i);
                    mask |= (1 << (ch - 'a'));
                }
                if (Integer.bitCount(mask) <= 7) {
                    frequency.put(mask, frequency.getOrDefault(mask, 0) + 1);
                }
            }

            List<Integer> ans = new ArrayList<Integer>();
            for (String puzzle : puzzles) {
                int total = 0;

                // 枚举子集方法一
                // for (int choose = 0; choose < (1 << 6); ++choose) {
                //     int mask = 0;
                //     for (int i = 0; i < 6; ++i) {
                //         if ((choose & (1 << i)) != 0) {
                //             mask |= (1 << (puzzle.charAt(i + 1) - 'a'));
                //         }
                //     }
                //     mask |= (1 << (puzzle.charAt(0) - 'a'));
                //     if (frequency.containsKey(mask)) {
                //         total += frequency.get(mask);
                //     }
                // }

                // 枚举子集方法二
                int mask = 0;
                for (int i = 1; i < 7; ++i) {
                    mask |= (1 << (puzzle.charAt(i) - 'a'));
                }
                int subset = mask;
                do {
                    int s = subset | (1 << (puzzle.charAt(0) - 'a'));
                    if (frequency.containsKey(s)) {
                        total += frequency.get(s);
                    }
                    subset = (subset - 1) & mask;
                } while (subset != mask);

                ans.add(total);
            }
            return ans;
        }
    }


    class Solution_Time_Exceed {
        public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
            Map<String, Integer> wordCountMap = new HashMap<>();
            for (String word : words) {
                int[] charCount = new int[26];
                for (char ch : word.toCharArray()) {
                    charCount[ch - 'a'] = 1;
                }

                String key = getCharCountKey(charCount);
                wordCountMap.put(key, wordCountMap.getOrDefault(key, 0) + 1);
            }

            List<Integer> res = new ArrayList<>();
            for (String puzzle : puzzles) {
                int curCount = 0;
                for (String key : wordCountMap.keySet()) {
                    if (isMatch(key, puzzle)) curCount += wordCountMap.get(key);
                }
                res.add(curCount);
            }

            return res;
        }

        public boolean isMatch(String key, String puzzle) {
            int[] puzzleArray = new int[26];
            for (char pc : puzzle.toCharArray()) {
                puzzleArray[pc - 'a'] = 1;
            }

            char puzzleFirstChar = puzzle.charAt(0);
            boolean isContainPuzzleFirstChar = false;
            for (char c : key.toCharArray()) {
                if (puzzleArray[c - 'a'] == 0) return false;
                if (c == puzzleFirstChar) isContainPuzzleFirstChar = true;
            }

            return isContainPuzzleFirstChar;
        }

        public String getCharCountKey(int[] charCount) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < charCount.length; i++) {
                if (charCount[i] == 1) sb.append(String.valueOf((char) ('a' + i)));
            }
            return sb.toString();
        }
    }

    public void run() {
        Solution solution = new Solution();
//        Wrong Answer:
//        input:["apple","pleas","please"]
//				["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
//        Output:[0,1,3,3,0]
//        Expected:[0,1,3,2,0]

        String[] words = InputUtil.toStringArray("[\"apple\",\"pleas\",\"please\"]");
        String[] puzzles = InputUtil.toStringArray("[\"aelwxyz\",\"aelpxyz\",\"aelpsxy\",\"saelpxy\",\"xaelpsy\"]");
        System.out.println(solution.findNumOfValidWords(words, puzzles));
    }

    public static void main(String[] args) throws Exception {
        LC1178 an = new LC1178();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
